\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{indentfirst}
\usepackage{amsmath}
\usepackage{longtable}
\pagenumbering{arabic}
\usepackage{setspace}

%\sloppy
\hyphenation{}

\begin{document}

\include{capa}

\tableofcontents
\newpage

\section{Introdução}

Temos verificado o aumento de pesquisas relacionadas ao desenvolvimento de algoritmos de inteligência artificial e a sua utilização em uma gama cada vez mais variada de aplicações. Talvez a mais notável destas aplicações seja a de jogos eletrônicos, com um mercado bilionário - comparável até mesmo à indústria cinematográfica.

Diversos mecanismos de inteligência artificial já foram desenvolvidos até hoje, cada um mais apropriado a um gênero específico de jogo. Neste trabalho, iremos ver alguns mecanismos simples, que também podem ser aplicados em outras áreas - incluindo a robótica.

\section{Objetivos}
Os objetivos deste trabalho são a implementação e o entendimento de dois algoritmos de navegação: O algoritmo de \textit{Perseguição} e o de \textit{Campos Potenciais}. A partir do cenário criado, com obstáculos e um goal (no caso do algoritmo de campos potenciais) ou um agente (em se tratando do algoritmo de perseguição), os NPCs têm que conseguir se desviar dos obstáculos e chegar ao local desejado.
 
O algoritmo utilizado nos Campos Potenciais foi o de cálculo da força resultante dos campos potenciais sobre cada NPC, incluindo a força de repulsão entre os próprios NPCs, enquanto a perseguição se baseou no \textit{Breadcumb algorithm}, onde o agente algo deixa uma certa quantidade de "migalhas" por onde passa, fazendo com que os NPCs siga esse rastro quando o enxergarem.

\section{Descrição do Problema}

Dado um certo ambiente, \textit{NPCS} (agentes autônomos) devem ser capazes de navegar através do cenário de forma autônoma, desviando de  obstáculos até encontrar o alvo da missão. Para isso é necessário a implementação de campos potenciais, no qual os \textit{Bots} são atraídos pelo objetivo (\textit{Goal}) e repelido pelos outros \textit{Bots} e obstáculos presentes no cenário.

O outro problema proposto é a perseguição e fuga. Neste caso um ou vários \textit{NPCS} devem perseguir um agente controlado pelo teclado ou mouse através do cenário.

\section{Proposta de Solução}

As soluções adotadas são bem simples. No caso dos campos potenciais é aplicado um algoritmo que é baseado na física clássica. É levado em consideração um conjunto de forças atuantes em cada \textit{NPC}, dadas pela equação $F=\frac{k}{d^2}$, onde $d$ é a distância entre os corpos interagindo. Dessa forma cada obstáculo e \textit{NPC} exerce uma força um sobre os outros. Há uma força principal de atração pelo objetivos da missão, que é um ponto no cenário, sendo assim, a resultante dessas forças faz com que os obstáculos sejam corretamente detectados e contornados e os Bos continuem sua trajetória a caminho do \textit{Goal}. É importante ressaltar que esta força tem um escopo de atuação limitado, que torna a simulação mais suave e jogável - o que não aconteceria caso forças exercidas por corpos muito distantes fossem sempre consideradas.

A solução para o caso da perseguição e fuga é fundamentado na mesma teoria que envolve os campos potenciais. Cada \textit{NPC} pode se locomover livremente no cenário à procura do seu agente (controlado por teclado). O agente por sua vez deixa um rastro no cenário para que os \textit{NPCS} autônomos possam encontrá-lo. O rastro deixado pelo agente é apagado com o tempo, sendo este tempo um parâmetro que pode ser ajustado, e assim um \textit{NPC} ao perceber uma "migalha" passa a perseguir o agente utilizando os campos potenciais para isso, ou seja, um vetor força direcionado para o agente faz com que cada \textit{NPC} siga em direção a ele.

\subsection{Algoritmo de Linhas}

\begin{center}
	\includegraphics[scale=0.50]{images/ilustracaoAlgReta.png}
	\captionof{figure}{Algoritmo de Linhas}
	\label{fig:retas}
\end{center}

Como já foi mencionado, os algoritmos desenvolvidos se baseiam na física clássica. O algoritmo implementado para as simulações relativas às retas são análogos ao problema de se calcular a força elétrica que uma barra eletricamente carregada exerce em um ponto a uma distância $d$.

O primeiro passo neste processo é calcular a distância $d$ entre o bot e a reta. Definimos uma distância mínima para a qual as forças serão calculadas, fazendo com que a reta seja ignorada caso o bot esteja muito distante dela. A fórmula para cálculo da distância entre um ponto a uma reta é a seguinte:
$$
d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}
$$

Após isso, a projeção que o bot realiza sobre a reta é calculada. Este passo é necessário para encontrar as distâncias das extremidades da barra à projeção - estas distâncias serão utilizadas na integral que nos dará a componente $y$ da força resultante. Para fins de simplificação, a componente $x$ não foi considerada. Esta projeção será utilizada, agora, para calcular os tamanhos $l_0$ e $l_1$ nos quais a reta é dividida.

A integral que desejamos será calculada tendo em vista a premissa de que a densidade linear de ``carga'' da barra é constante (isto é, a quantidade de carga pela unidade de comprimento é a mesma em todos os pontos da barra). A fórmula para o cálculo da componente y é uma generalização da fórmula demonstrada no livro \textit{Physics for Scientists and Engineers: Solution Manual}, sexta edição, problema 23.35, e é dada a seguir:
$$
F_y = \frac{l_0}{d^2 \sqrt{l_0^2 + d^2}}-\frac{l_1}{d^2 \sqrt{l_1^2 + d^2}}
$$

Por fim, devemos rotacionar o vetor resultante para o ângulo adequado, dado pela reta que liga o Bot à sua projeção na reta. O vetor final é dado pelo produto do vetor $(0,F_y)$ pela matriz de rotação, dada por:
$$
\begin{pmatrix}
 \cos \Theta & -\sin \Theta \\
\sin \Theta & \cos \Theta
\end{pmatrix}
$$

O ângulo $\Theta$ foi calculado com o coeficiente angular da reta (que é justamente a tangente do ângulo feito com o eixo $x$) através das seguintes relações trigonométricas:
$$
1 + tan^2 \alpha = \frac{1}{cos^2 \alpha}
$$
$$
1 + cot^2 \alpha = \frac{1}{sen^2 \alpha}
$$


\section{Decisões de Implementação}

No algoritmo de migalhas de pão é escolhida no menu o tamanho da cauda que o agente movido pela pessoa irá deixar. O NPC, ao perceber essa cauda, chegando a uma certa distância do rastro, começará a a ser atraído, indo em direção ao agente. Quando o \textit{Bot} atingir o \textit{Goal} (agente) a resultante das forças será nula, e a velocidade irá cessar, voltando a se mover apenas quando ele sair da posição que é a mesma do agente.

Para a implementação dos movimentos aleatórios dos \textit{Bots}, no caso de procura pelo agente, foi adotado um estratégia bem simples, mas eficiente. Ao iniciar a simulação com perseguição, todo \textit{Bot} que está no cenário e aqueles que forem adicionados depois passar a executar movimentos aleatórios. Esse movimentos são criados da seguinte forma: todo NPC decide se ele vai alterar a direção de seu movimento corrente, e isso é feito através de uma função randômica. Caso ele deva alterar a direção/sentido, ele gera um vetor temporário randômico de força, em que as componentes incrementam a velocidade na direção $x$ e na direção $y$. Um contador define o tempo em que essa força irá atuar sem que seja substituída por outra, ou seja, uma força constante durante um período de tempo. A cada tempo esse contador é decrementado e quando ele chega a zero, uma nova força pode ser aplicada ou não, dependendo da decisão do \textit{Bot} em aplicar tal força. Dessa forma esse mantém um movimento aleatório que o faz mover por todo o cenário.


\section{Compilação e Execução}
\subsection{Compilação}
Para compilação do projeto faça uso do utilitário \textit{make} dentro da pasta raiz do projeto em um ambiente \textit{Linux}. Primeiramente execute o comando ``make clean" e depois ``make run" para executar o aplicativo. A compilação pode estendida como a seguir:

\begin{verbatim}

cd src; javac -d ../build/classes */*.java; 
            cp -rp images/ ../build/classes
cp Manifest.mf build/classes
echo "Main-Class: simulador.Main" >> 
                  build/classes/Manifest.mf
cd build/classes; jar cfm Simulador.jar
               Manifest.mf */*.class images/*
cp build/classes/Simulador.jar dist/
\end{verbatim}

O executável \textit{Simulador.jar} pode ser executado em qualquer máquina que possuir a máquina virtual Java, mas a compilação é exclusiva para o \textit{Linux}.

\subsection{Interface do Programa}
A interface gráfica do programa foi feita em Java usando as bibliotecas padrões do Java \textit{javax.swing}. A Figura \ref{fig:interface} mostra a interface simples adotada para o simulador. Apesar de ser simples, fornece uma boa flexibilidade de configuração do cenário para os tipos de simulação suportados.

\begin{center}
	\includegraphics[scale=0.4]{images/interface.png}
	\captionof{figure}{Interface do Programa}
	\label{fig:interface}
\end{center}

\subsubsection{Funcionalidades}
O simulador pode ser ajustado para prover um ambiente mais realista de acordo com o que deseja simular. A barra de ferramentas possui os recursos mais comuns, que serão amplamente utilizados em qualquer simulação.

\begin{center}
	\includegraphics[scale=0.4]{images/toolbar.png}
	\captionof{figure}{Barra de Ferramentas}
	\label{fig:toolbar}
\end{center}

Os botões que estiverem ativos poderão ser usados durante a simulação. Caso algum elemento não seja aplicável ao algoritmo de simulação, a interface irá bloquear o recurso, a fim de que não haja enganos na utilização do software.

\subsubsection{Parâmetros}

Os seguintes parâmetros podem ser alterados na execução do programa. Para as próximas versões eles serão ampliados.

\begin{center}
	\includegraphics[scale=0.4]{images/options.png}
	\captionof{figure}{Tela de Opções}
	\label{fig:options}
\end{center}

A densidade da linha se refere à constante de força de repulsão das retas no cenário.

\subsubsection{Modo de Operação}
Ao iniciar uma simulação, todo o ambiente estará submetido a alterações que por ventura sejam feitas no cenário. Desde as atualizações das constantes até a mudança do algoritmo da simulação. Para observar esse comportamento basta mudar alguma propriedade do Simulador que será possível perceber que os algoritmos são atualizados e passam a agir instantaneamente.

\section{Testes Realizados}

Algumas configurações de cenário e algoritmo foram propostas a fim de legitimar o funcionamento do programa. 

A Figura \ref{fig:simple_potential} mostra o caso em que temos um esquema de campos potenciais simples. Seja o objetivo o círculo preto, os obstáculos (verdes) repelem os \textit{NPCS} que repelem entre si. O somatório das forças atuantes em cada \textit{Bot}, aliado ao vetor força que aponta para o \textit{Goal}, direciona cada \textit{Bot} para o objetivo.

\begin{center}
	\includegraphics[scale=0.4]{images/potencial.png}
	\captionof{figure}{Campos Potencias Simples}
	\label{fig:simple_potential}
\end{center}

Já a Figura \ref{fig:complex_potential} mostra um esquema de repulsão e atração mais complexo. Neste caso estão envolvidas retas e seus respectivos campos potenciais que atuam sobre o ambiente. O cálculo dessas forças são bem complexos e já foram bem detalhados anteriormente no texto.

\begin{center}
	\includegraphics[scale=0.4]{images/repulsiveLines.png}
	\captionof{figure}{Campos Potenciais Complexos com Retas}
	\label{fig:complex_potential}
\end{center}

O segundo algoritmo proposto para implementação foi o de Perseguição e Fuga. A Figura \ref{fig:chase} mostra uma configuração que os \textit{Bots} ao verem migalhas do agente espalhadas no ambiente passam a correr atrás do agente. Antes disso todos os \textit{Bots} executam movimentos aleatórios.

\begin{center}
	\includegraphics[scale=0.4]{images/chase.png}
	\captionof{figure}{Algoritmo de Perseguição e Fuga}
	\label{fig:chase}
\end{center}


O interessante a ser observado no Simulador implementado é que está altamente modularizado e pronto para eventuais extensões. Cada \textit{Bot}, agente, obstáculo é um objeto independente que calculam as forças que atuam em cima deles. Além disso, as técnicas utilizadas para os dois algoritmos se assemelham muito e promoveram robustez ao programa, que submetido a configurações de cenário diversas, comportou-se de maneira lógica, adequando-se ao esperado por cada algoritmo.

\section{Conclusões}

Algoritmos de Inteligência Artificial possuem características bastante interessantes, tais como as que foram vistas no desenvolvimento deste trabalho. O algoritmo de Campos potenciais fornece ao jogo uma boa impressão de que os \textit{Bots} estão agindo por conta própria. O fato de que a trajetória a ser seguida depender da posição de cada um no cenário faz com que a mesma trajetória seja praticamente impossível para dois ou mais \textit{NPCS}. O resultante das forças atuantes em cada um será sempre diferente, o que torna o estudo do algoritmo uma tarefa muito interessante.

Foi possível notar que aliando estratégias (algoritmos) podemos construir comportamentos bem reais para um agente qualquer. No caso da perseguição, os campos potenciais atrelados à lógica forneceu ferramenta simples para implementação do algoritmo, ficando como parte mais difícil a modelagem do comportamento dos \textit{Bots} quando não há perseguição.

Todos os algoritmos implementados foram de grande importância para o conhecimento de formas de comportamento de agentes em jogos. E como trabalho futuro, acredito que isso será de extrema importância para aprimorar o Simulador para suportar novos algoritmos que venham a ser implementados.

%\nocite{*}
%\bibliographystyle{plain}
%\bibliographystyle{apalike}
%\renewcommand{\refname}{Referências} 

\section{Referências}
\begin{enumerate}
	\item Transparências da Disciplina;
\end{enumerate}
%\bibliography{referencias}

\end{document}
